/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        //1 2 4 3
        if(head == null || head.next == null) {
            return;
        }
        ListNode mid = findCenter(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next=null;
        l2 = reverseList(l2);
        mergeList(l1,l2);
    }
    //先找到中点
    private ListNode findCenter(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null && fast.next.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    //再进行翻转
    private ListNode reverseList(ListNode head) {
        ListNode node = head.next;
        head.next = null;
        while(node!=null) {
            ListNode tem = node.next;
            node.next = head;
            head = node;
            node = tem;
        }
        return head;
    }
    //最后进行合并
    private void mergeList(ListNode head1,ListNode head2) {
        ListNode n1 = head1;
        ListNode n2 = head2;
        //先放head1
        //指向合并的新的链表
        while(n1!= null && n2!=null) {
            ListNode tem1 = n1.next;
            ListNode tem2 = n2.next;
            
            n1.next = n2;
            n1 = tem1;
            n2.next = n1;
            n2 = tem2;

        }

    }
}